The invention relates to methods and apparatus for improving routing in packet networks and, more particularly, to methods and apparatus for improving generic call admission control and for reducing computational loads associated with route selection.
It is known that ATM (Asynchronous Transfer Mode) technology has been undergoing intense standardization efforts in recent years under both the ITU (International Telecommunications Union) and the ATM Forum. For example, a set of specifications relating to routing and signaling protocols for an ATM private network-to-network interface (PNNI) has been developed by the ATM Forum, i.e., ATM Forum, xe2x80x9cPrivate Network-Network Specification Interface 1.0,xe2x80x9d af-tm-0055.000 (March 1996).
In the PNNI framework, network nodes (switches) constantly send updates on the status of their local links to all other nodes in the network. These updates are sent periodically and/or triggered by changes in link attributes such as the available bandwidth or cell rate (AvCR) of the link. While some link attributes, such as available bandwidth, change frequently as calls arrive and depart, certain others remain relatively constant. For example, administrative weights (AW) associated with links fall into the latter category. These weights can be manipulated by network operators via the network management system and are meant to guide the route selection algorithms in selecting least AW cost paths. Based on the updates received, each network node constructs its own topological view of the network. Routes through the network are independently computed by each originating (source) node based on its view of the network. Upon a call origination, the source node needs to check if the candidate route satisfies the requirements of the current call in terms of, for example, quality of service (QoS) requirements given its traffic descriptors. QoS requirements include, for example, bandwidth and delay requirements. This check is referred to as generic call admission control (GCAC). In addition, network nodes along the path of the call (intermediate nodes) perform their own call admission control referred to as local call admission control (LCAC).
It is known that there are numerous performance issues in PNNI routing. They can be broadly categorized as addressing two types of limiting resources, namely: real-time resources, e.g., call processor (CPU) utilization in the switch control complex; and the cell transport resources, e.g., transmission bandwidth of a link. The demands for real-time resources stem from handling call set-up/teardowns including path selection at the source switches, performing call admission control at the local switches, and processing incoming and outgoing link state advertisements. The performance is measured primarily in terms of the amount of real-time resources required to handle a given load and the resultant processing delay characteristics. Given a network, this performance is a strong function of the design/implementation of the related algorithms, the computational cost of the chosen algorithms and the settings of the tunable parameters. Limiting transport resources include switch cell buffers and link bandwidth required to support the desired QoS of the admitted calls.
Due to the source routing nature of PNNI, the design of the routing algorithm has a direct impact on how efficiently the network links are utilized. Further, given a distributed architecture in which switches, possibly from different vendors, independently compute routes, ill-advised route selections may result in excessive crankbacks or rejections of call set-up requests and, subsequently, create unnecessary real-time load on the call processors associated with the node or switch.
Under the PNNI architecture, a source switch has to select a candidate path such that there is a reasonably high probability for all the switches along the accepted path to accept the call. Otherwise, as mentioned above, a substantial amount of crankback or rejection can result which unnecessarily consumes network and switch resources while increasing call set-up delays. It is therefore necessary for a source switch to estimate the availability of various resources at other switches within the network. It is known that such estimation can only be based on the limited and possibly outdated information derived from previous switch update advertisements. The exact penalty and tradeoff depends on the frequency of link state update advertisements and the algorithms used for GCAC at the source switch and LCAC at the intermediate switches.
Assume a link of capacity C and homogenous connections (calls) arriving at the link. Let Nmax denote the maximum number of connections that can be supported on the link according to the LCAC. Let ebwlcac=C/Nmax denote the effective bandwidth connection according to LCAC. Similarly, let ebwgcac denote the per-connection effective bandwidth according to GCAC. Let N(t) denote the current number of connections admitted to the link. Then Cxe2x88x92N(t)*ebwlcac is the available bandwidth, denoted as AvCR, at the link and is the value advertised in the link state update by the node to which the link is coupled. Note that in GCAC, it is this AvCR value that is compared to the effective connection bandwidth computed by the GCAC. Thus, the probability that a connection is blocked by the GCAC is given by:                                                         P                              b                ⁢                                  xe2x80x83                                ⁢                l                ⁢                                  xe2x80x83                                ⁢                o                ⁢                                  xe2x80x83                                ⁢                c                ⁢                                  xe2x80x83                                ⁢                k                                      =                                                            P                  ⁢                                      xe2x80x83                                    ⁢                  (copyright)                                -                                                      N                    ⁡                                          (                      t                      )                                                        *                  e                  ⁢                                      xe2x80x83                                    ⁢                  b                  ⁢                                      xe2x80x83                                    ⁢                                      w                                          l                      ⁢                                              xe2x80x83                                            ⁢                      c                      ⁢                                              xe2x80x83                                            ⁢                      a                      ⁢                                              xe2x80x83                                            ⁢                      c                                                                                   less than                               e                ⁢                                  xe2x80x83                                ⁢                b                ⁢                                  xe2x80x83                                ⁢                                  w                                      g                    ⁢                                          xe2x80x83                                        ⁢                    c                    ⁢                                          xe2x80x83                                        ⁢                    a                    ⁢                                          xe2x80x83                                        ⁢                    c                                                                                )                                              =                      P            ⁡                          (                                                                    N                    ⁡                                          (                      t                      )                                                        *                  e                  ⁢                                      xe2x80x83                                    ⁢                  b                  ⁢                                      xe2x80x83                                    ⁢                                      w                                          l                      ⁢                                              xe2x80x83                                            ⁢                      c                      ⁢                                              xe2x80x83                                            ⁢                      a                      ⁢                                              xe2x80x83                                            ⁢                      c                                                                       less than                                   C                  -                                      e                    ⁢                                          xe2x80x83                                        ⁢                    b                    ⁢                                          xe2x80x83                                        ⁢                                          w                                              g                        ⁢                                                  xe2x80x83                                                ⁢                        c                        ⁢                                                  xe2x80x83                                                ⁢                        a                        ⁢                                                  xe2x80x83                                                ⁢                        c                                                                                                        )                                                                    =                      P            ⁡                          (                                                N                  ⁡                                      (                    t                    )                                                   greater than                                                       N                    max                                    -                                      e                    ⁢                                          xe2x80x83                                        ⁢                    b                    ⁢                                          xe2x80x83                                        ⁢                                                                  w                                                  g                          ⁢                                                      xe2x80x83                                                    ⁢                          c                          ⁢                                                      xe2x80x83                                                    ⁢                          a                          ⁢                                                      xe2x80x83                                                    ⁢                          c                                                                    /                      e                                        ⁢                                          xe2x80x83                                        ⁢                    b                    ⁢                                          xe2x80x83                                        ⁢                                          w                                              l                        ⁢                                                  xe2x80x83                                                ⁢                        c                        ⁢                                                  xe2x80x83                                                ⁢                        a                        ⁢                                                  xe2x80x83                                                ⁢                        c                                                                                                        )                                            "AutoLeftMatch"
These relationships suggest that if ebwgcac greater than ebwlcac, the GCAC is conservative as compared to LCAC, and if Nmax is much larger than ebwgcac/ebwlcac, which is typically the case, then loss of utilization due to GCAC may be negligible. However, if the ebwgcac is estimated by the source node to be too conservative, i.e., using a higher effective bandwidth than necessary so that there is a buffer, there is a risk that links associated with intermediate switches would not be utilized. On the other hand, if GCAC is aggressive compared to LCAC, then depending on the difference, there can be an undesirably large number of crankbacks. In fact, even if the GCAC and the LCAC are exactly the same, i.e., ebwgcac=ebwlcac, it is still possible to get crankbacks due, for example, to delays in the link state updates reaching all network nodes and the fact that the updates are typically only generated when there are significant changes in the network state.
Since a path chosen by a source node will likely pass through more than one link in order to get to the destination node, the available bandwidth associated with the path is characterized by the link having the smallest available bandwidth, as illustrated by the Pblock equation above. Thus, in order for the source node to characterize a path as sufficient to set-up the call on, the relationship AvCRxe2x89xa7ebwgcac must be satisfied for each link. Various ATM classes of service choose an equivalent bandwidth (ebwgcac) definition. For example, as suggested in the above-referenced PNNI standard, the CBR (constant bit rate) class uses the PCR (peak cell rate) as an equivalent bandwidth. The VBR (variable bit rate) class uses the relationship of SCR[1+(PCR/SCR)], where SCR is the sustained or mean cell rate. The ABR (available bit rate) class uses the MinCR (minimum cell rate). However, each of these definitions may range from too conservative to too aggressive and, thus, suffer from the drawbacks mentioned above. Accordingly, it would be highly advantageous to provide methods and apparatus for selecting an appropriate GCAC equivalent bandwidth which results in minimization of crankbacks, while maximizing utilization of intermediate links.
Furthermore, it is known that the route selection at the source node requires a non-trivial amount of real-time resources to perform the required computations. The conventional process provides that when a call comes in to a source node, there is typically only one path stored for the call to reach the desired destination node. The source node tests all the links in this path to determine if the path satisfies the requirements, e.g., QoS and traffic descriptor, of the call. If the path satisfies the requirements, the call is set-up on this path. However, if the stored path does not satisfy the requirements and the source node has knowledge of the current network topology, the source node computes and tests a new path. This is repeated until a suitable path is found.
A significant problem with the above procedure is that finding (computing) a new path each time a new call comes in to the source node burdens the processing resources at the source node. Disadvantageously, the processor of the source node may be the reason that a call is blocked. Accordingly, it would be highly advantageous to provide methods and apparatus for reducing the computational load on the processing resources of the source node during route selection.
The present invention provides methods and apparatus for performing GCAC which advantageously results in minimization of crankbacks and maximization of link utilization. In one aspect of the invention, a packet switch is configured for determining an equivalent bandwidth for use in GCAC. The equivalent bandwidth definition of the invention is derived by multiplying some known connection parameter such as, for example, a selected bandwidth value (e.g., in the case of ATM CBR service, the PCR) by a multiplier preferably computed and stored in look-up tables according to the invention. The appropriate multiplier for a given connection request associated with a call may then be found by accessing sets of the look-up tables based on one or more connection parameters, for example, a QoS parameter such as a delay requirement and/or a traffic descriptor. For each link in a path considered during GCAC, the product of the multiplication of the selected bandwidth value and the multiplier is then compared to the available bandwidth, AvCR, of the link. If the AvCR is greater than or equal to the product, then the connection is set-up on that path, if not, the connection request is rejected. In another aspect of the invention, the GCAC is performed as a function of network-related parameters such as, for example, the number of connections associated with a given link at a given point in time and the current utilization of the link capacity.
Furthermore, the present invention provides methods and apparatus for reducing the computational load on processing resources of a source node during route selection. In one aspect of the invention, a packet switch is configured with the capability of caching more than one candidate path of a network. The packet switch is also configured for testing at least one cached candidate path upon receipt of a connection request associated with a call to determine if the cached candidate path satisfies the connection request. If one of the cached paths satisfies the connection request, then the call is set-up on that path. If not, the packet switch performs a real-time computation to find a new path. If a new path which satisfies the connection request is found, the call is set-up thereon and the newly computed path is cached according to a predetermined ordering/replacement policy. The policy may be a function of certain metrics such as, for example, the administrative weight and the available bandwidth associated with a path.